package dichotomy.nextgreatestletter;
/**
 * @Date 2020/1/23
 * @author 王光浩
 * @Need 给定一个升序排序的小写字符数组，与一个target字符，在数组中找出第一个比target大的字符（如果没有找到就返回第一个字符数组内容，自己理解后的解释），数组最少包含两个不同的字符，长度在2到10000之间
 * @Thinking 使用二分法。第一种二分法。
 *           时间复杂度O（logn），空间复杂度O（1）
 */
public class MyMethodTwo {
    public char nextGreatestLetter(char[] letters, char target) {
    	int later=letters.length-1;
    	int previous=0;
    	int mid;
    	while(later>=previous) {
    		mid=previous+(later-previous)/2;
    		if(target<letters[mid])
    			later=mid-1;
    		else
    			previous=mid+1;
    	}
    	return letters[previous%letters.length];  //
    }

}
